﻿using System;
using System.Collections;
using System.Collections.Generic;

namespace JiShiBen.Core.DataStructure
{
	public abstract class DoublyLinkedList<T> : IEnumerable<DoublyLinkedList<T>.DoublyLinkedListNode> where T : DoublyLinkedList<T>.DoublyLinkedListNode
	{
		#region Constructor

		protected DoublyLinkedList()
		{
			_first = null;
			_last = null;
			_version = int.MinValue;
		}

		#endregion

		#region Private Members

		#region Fields

		protected readonly object _syncObject = new object();

		private int _version;
		private DoublyLinkedListNode _first;
		private DoublyLinkedListNode _last;
 
		#endregion


		#region Methods

		private void IncreaseVersion()
		{
			_version++;
			if (_version == int.MaxValue)
				_version = int.MinValue;
		}

		#endregion

		#endregion


		#region Protected Members

		#region Methods

		protected virtual void InsertAfter(T node, T newNode)
		{
			if (newNode == null)
				throw new ArgumentNullException("newNode");

			if (node == null)
			{
				InsertEnd(newNode);
				return;
			}

			if (!Contains(node))
				throw new InvalidOperationException("Node does not exists.");

			newNode.Previous = node;
			newNode.Next = node.Next;
			if (node.Next == null)
				_last = newNode;
			else
				node.Next.Previous = newNode;
			node.Next = newNode;

			IncreaseVersion();
		}

		protected virtual void InsertBefore(T node, T newNode)
		{
			if (newNode == null)
				throw new ArgumentNullException("newNode");

			if (node == null)
			{
				InsertBegin(newNode);
				return;
			}

			if (!Contains(node))
				throw new InvalidOperationException("Node does not exists.");

			newNode.Next = node;
			newNode.Previous = node.Previous;
			if (node.Previous == null)
				_first = newNode;
			else
				node.Previous.Next = newNode;
			node.Previous = newNode;

			IncreaseVersion();
		}

		protected virtual void InsertBegin(T node)
		{
			if (node == null)
				throw new ArgumentNullException("node");

			if (IsEmpty)
			{
				_first = node;
				_last = node;
			}
			else
			{
				var temp = _first;
				_first = node;
				_first.Next = temp.CastToChildType();
				temp.Previous = _first.CastToChildType();
			}

			IncreaseVersion();
		}

		protected virtual void InsertEnd(T node)
		{
			if (node == null)
				throw new ArgumentNullException("node");

			if (IsEmpty)
			{
				_first = node;
				_last = node;
			}
			else
			{
				var temp = _last;
				_last = node;
				_last.Previous = temp.CastToChildType();
				temp.Next = _last.CastToChildType();
			}

			IncreaseVersion();
		}

		protected virtual void Remove(T node)
		{
			if (node == null)
				throw new ArgumentNullException("node");

			if (!Contains(node))
				throw new InvalidOperationException("Node does not exists.");

			if (node == _first)
			{
				_first = _first.Next;
				_first.Previous = null;
				node.Next = null;
			}
			else if (node == _last)
			{
				_last = _last.Previous;
				_last.Next = null;
				node.Previous = null;
			}
			else
			{
				var prev = node.Previous;
				var next = node.Next;
				prev.Next = next;
				next.Previous = prev;
				node.Previous = null;
				node.Next = null;
			}

			node.Dispose();
			IncreaseVersion();
		}

		protected bool Contains(T node)
		{
			var result = false;
			var temp = _first;
			do
			{
				if (temp == node)
				{
					temp = null;
					result = true;
				}
				else
					temp = temp.Next;
			} while (temp != null);

			return result;
		}

		internal protected int GetNextUniqueIdentification()
		{
			lock (_syncObject)
			{
				var rand = new Random();
				if (IsEmpty)
					return 0;

				var temp = _first;
				int result;
				do
				{
					result = rand.Next();
					temp = temp.Identification == result ? temp.Next : null;
				} while (temp != null);

				return result;
			}
		}

		protected DoublyLinkedListNode GetFirst()
		{
			return _first;
		}

		protected DoublyLinkedListNode GetLast()
		{
			return _last;
		}

		#endregion

		#endregion


		#region Public Members

		#region Properties

		public bool IsEmpty { get { return _first == null; } }

		#endregion


		#region Methods

		public abstract void Clear();

		public IEnumerator<DoublyLinkedListNode> GetEnumerator()
		{
			return new ListNodeEnumerator(this);
		}

		#endregion

		#endregion


		#region Explicit Interface Implementation

		IEnumerator IEnumerable.GetEnumerator()
		{
			return GetEnumerator();
		}

		#endregion


		#region Sub Type

		public class ListNodeEnumerator : IEnumerator<DoublyLinkedListNode>
		{
			private readonly DoublyLinkedList<T> _list;
			private readonly int _version;
 
			public ListNodeEnumerator(DoublyLinkedList<T> list)
			{
				if (list == null)
					throw new ArgumentNullException("list");

				_list = list;
				_version = list._version;
			}

			public DoublyLinkedListNode Current { get; private set; }

			public void Dispose()
			{
				Current = null;
			}

			object IEnumerator.Current
			{
				get { return Current; }
			}

			public bool MoveNext()
			{
				if (_version != _list._version)
					throw new InvalidOperationException("The collection was modified after the enumerator was created.");

				if (_list.IsEmpty)
					return false;

				Current = Current == null ? _list.GetFirst() : Current.Next;

				return Current != null;
			}

			public void Reset()
			{
				Current = _list._first;
			}
		}

		public abstract class DoublyLinkedListNode
		{

			#region Constructor

			protected DoublyLinkedListNode(DoublyLinkedList<T> list)
			{
				if (list == null)
					throw new ArgumentNullException("list");

				Identification = list.GetNextUniqueIdentification();
			}

			#endregion


			#region Protected Members

			protected abstract void Dispose(bool disposing);

			public abstract T CastToChildType();

			#endregion


			#region Public Members

			#region Properties

			public int Identification { get; private set; }

			public abstract T Previous { get; set; }

			public abstract T Next { get; set; }

			#endregion


			#region Methods

			public override bool Equals(object obj)
			{
				var temp = obj as DoublyLinkedListNode;
				if (Equals(temp, null)) return false;

				return temp.GetHashCode() == GetHashCode();
			}

			public override int GetHashCode()
			{
				return Identification;
			}

			public void Dispose()
			{
				Dispose(true);
			}

			#endregion

			#endregion
		}

		#endregion
	}
}
